This invention relates to an encryption device for performing encoded communication in home banking, farm banking and electronic mail in a computer network and in various communication services such as electronic conferencing. Furthermore, the invention relates to an encryption device for performing encrypted communication using an encryption method that employs modular multiplication (quadratic residual ciphers, RSA ciphers, ElGamal ciphers, etc.), a key distribution method (DH-type key distribution method, an ID-based key distribution method, etc.), a zero-knowledge authentication system, etc.
Further, the invention relates to a communication method and apparatus which employ random-number generation necessary in encrypted communication, particularly data concealment, originator/terminator authentication, distribution of encryption key and a zero-knowledge authentication protocol, etc. The invention relates also to a method and apparatus for random-number generation as necessary in a Monte Carlo simulation, by way of example.
The importance of cryptographic techniques to protect the content of data has grown with the rapid advances that have recently been made in information communication systems using computer networks. In particular, high-speed encryption is becoming essential as computer networks are being developed for higher speed and larger volume.
Among the foregoing, modular multiplication is a particularly important operation used in various cryptographic techniques. Various methods of encryption using modular multiplication will now be described.
Two methods of encryption which are well known are a secret-key cryptosystem and a public-key cryptosystem.
In a public-key cryptosystem, the encryption and decryption keys differ. The encryption key is known publicly but the decryption key is held in secrecy by the receiving party and it is difficult to infer the decryption key from the publicly disclosed encryption key. Ciphers based upon modular multiplication, such as RSA ciphers and ElGamal ciphers, are used widely in public-key cryptosystem. Attention is being given to the fact that these ciphers have an application called authentication in addition to a secret communication function. Authentication, which is a function for investigating whether a party transmitting communication text is correct or not, is also referred to as a digital signature. In a digital signature which uses these ciphers, secret signatures known only to the transmitting party are possible and cannot be forged. Accordingly, a digital signature is secure and often finds use as a form of authentication communication in financial facilities.
In a secret-key cryptosystem, in which the same key is shared in secrecy by both the sending and receiving parties, use is made of random numbers referred to as quadratic residues obtained from an operation employed in modular multiplication.
The above-mentioned public-key cryptosystem and secret-key cryptosystem methods are often used together with a key-delivery system or key distribution system. A well known example of the key-delivery system is DH-type key delivery developed by Diffie and Hellman. These systems also implement operations using modular multiplication. Furthermore, an ID-based key distribution method is attracting attention as a key distribution method. Modular multiplication is used in various key distribution methods.
In addition, zero-knowledge authentication is available as an encryption technique. This is a method in which one party convinces another party of the fact that it possesses certain knowledge without letting the other party know of the content of the information.
The details of the foregoing are described in "Modern Cryptographic Theory" [Denshi Joho Tsushin Gakkai (1986)], by Shinichi Ikeno and Kenji Koyama, and "Cryptography and Information Security", Shokodo (1990)], by Shigeo Tsujii and Masao Kasahara.
It should be appreciated from the foregoing that if an efficient modular multiplication circuit and method can be realized, this will make it possible to implement a variety of encryption systems efficiently.
A technique referred to as the Montgomery method (Montgomery, P. L: "Modulator Multiplication without Trial Division", Math. Of Computation, Vol. 44, 1985, pp. 519.about.521) is known as a method of performing modular multiplication of P=A.multidot.B.multidot.R.sup.-1 mod N (where R and N are relatively prime integers) The Montgomery method makes it possible to perform modular multiplication without division. This will now be described.
[Description of Montgomery Method]
A theorem derived by Montgomery is as follows: "When N and R are relatively prime integers and N'=-N.sup.-1 mod R holds, arbitrary integers T, (T+M.multidot.N)/R satisfy the following relationship: EQU (T+M.multidot.N)/R=T.multidot.R.sup.-1 mod N (A-1)
where M=T.multidot.N' mod R holds.
In accordance with the Montgomery method, therefore, in a case where modular multiplication: P=A.multidot.B.multidot.R.sup.-1 mod N is to be executed, this can be carried out in the manner EQU P=A.multidot.B.multidot.R.sup.-1 mod N=(A.multidot.B+M.multidot.N)/R(A-2)
where EQU M=A.multidot.B.multidot.N' mod R (A-3)
using an integer R which is prime with respect to N.
In a case where N is an odd number, R is a prime integer with respect to N if R=2.sup.r (where r is any integer) holds. In this case, division by R entails a bit shift only and, hence, the operation of Equation (A-2) can be executed in simple fashion by multiplication and addition.
With the Montgomery method, however, cases arise in which the range of output values of modular multiplication becomes larger than the range of input values. For example, letting the ranges of the values of inputs A and B be expressed by EQU 0.ltoreq.A, B&lt;N
the operation of the Montgomery method indicated by Equations (A-2), (A-3) EQU P=(A.multidot.B+M.multidot.N)/R=(C+M).multidot.N/R
where C=A.multidot.B/N is executed.
If C+M&gt;R holds in this case, then (C+M)/R&gt;1 will hold and we will have EQU P=(A.multidot.B+M.multidot.N)/R&gt;N
That is, there will be cases in which a value P&gt;N is outputted with respect to inputs of 0&lt;A, B&lt;N.
As a consequence, it is difficult to repeat modular multiplication by a circuit or method which implements the Montgomery method. Further, the operation of modular multiplication generally used in cryptographic techniques is EQU Q=A.multidot.B mod N
In order to realize such modular multiplication, it is necessary to repeat the Montgomery method a plurality of times. This makes it difficult to execute this operation efficiently using the Montgomery method.
Further, with regard to a sequence of random numbers used in encrypted communication, it is required that random numbers generated after a certain point in time not be readily predictable from a sequence of random numbers generated up to this point in time. In the literature "Primality and Cryptography" (by Evangelos Kranakis, published by John Wiley & Sons, pp. 108.about.137), a sequence of pseudorandom numbers satisfying the above-mentioned requirement is described.
Specifically, if we let a sequence of pseudorandom numbers be represented by b.sub.1, b.sub.2, . . . , a bit b.sub.i is given by EQU X.sub.i+1 =X.sub.i.sup.2 mod N (i=0, 1, 2, . . . ) (B-1) EQU b.sub.i =lsb(X.sub.i) (i=1, 2, . . . ) (B-2)
where X.sub.0 is an initial value given arbitrarily and p, q are prime numbers in which p.ident.q.ident.3 (mod 4) holds (it should be noted that N=p.multidot.q holds and lsb represents least significant bit). A different method of generating a sequence of pseudorandom numbers is described in the literature "Cryptography and information Security" (by Shigeo Tsujii and Masao Kasahara, published by Shokodo, pp. 86).
Specifically, if we let a sequence of pseudorandom numbers be represented by b.sub.1, b.sub.2, . . . , a bit b.sub.i is given by EQU x.sub.i+1 =x.sub.i.sup.e mod N (i=0, 1, 2, . . . ) (B-3) EQU b.sub.i =lsb(x.sub.i) (i=1, 2, . . . ) (B-4)
where x.sub.0 is an initial value given arbitrarily p, q are prime numbers and e is a relatively prime number with respect to L (L is a least common multiple of p-1 and q-1). N=p.multidot.q holds and lsb represents least significant bit.
It is known that obtaining b.sub.i+1 solely from the sequence of pseudorandom numbers b.sub.1, b.sub.2, . . . , b.sub.i generated by these methods would require an amount of labor tantamount to that needed to factorize N. In other words, it is known that the amount of computation for obtaining pseudorandom numbers to be generated from a certain point in time onward from a sequence of pseudorandom numbers generated up to this point in time is equivalent to the amount of computation needed to factorize N. However, in order to make the factorization of N difficult in terms of amount of computation, it is required that p, q be made of several hundred bits. Random numbers thus generated by a method through which it is made difficult, in terms of amount of computation, to predict random numbers to be generated from a certain point in time onward from a sequence of random numbers generated up to this point in time are referred to as pseudorandom numbers considered cryptologically secure.
The operations of Equations (B-1) and (B-3) are included in the operation referred to as modular multiplication indicated by the following equation: EQU Q=.upsilon..multidot..nu. mod N (B-5)
(where Q, .upsilon., .nu. are integers.)
The above-mentioned Montgomery method is known as a method of performing modular multiplication efficiently. If the Montgomery method is used, the operation can be carried out without performing division by modulus N. As a result, processing can be executed more efficiently than with ordinary modular multiplication.
If we let modular multiplication for a case in which the Montgomery method is used be represented by Mont (.upsilon., .nu.), then Mont (.upsilon., .nu.) will be given by EQU Mont (.upsilon., .nu.).ident..upsilon..multidot..nu..multidot.R.sup.-1 (mod N) (B-6)
using R, which is a relatively prime number with respect to N.
In order to obtain the computational result Mont (.upsilon., .nu.) of the above equation with the Montgomery method, the following operation is carried out: EQU Mont (.upsilon., .nu.)=(.upsilon..multidot..nu.+M.multidot.N)/R(B-7)
where EQU M=.upsilon..multidot..nu..multidot.N' mod R (B-8) EQU N'=-N.sup.-1 mod R (B-9)
In a case where N is an odd number, R and N are relatively prime integers if R=2.sup.t (where t is any integer) holds. In this case, division by R and modular multiplication essentially need not be performed and Mont (.upsilon., .nu.) can be executed at high speed solely by multiplication and addition.
The procedure for performing a quadratic residue operation in a case where the Montgomery method is used is given by EQU y.sub.0 =R.multidot.X.sub.0 mod N (B-10) EQU y.sub.i+1 =R.sup.-1 .multidot.y.sub.i.sup.2 mod N (i=0, 1, 2, . . . )(B-11)
using the same parameters as in Equation (B-1) and R, which is a relatively prime number with respect to N.
In this case, when the sequences generated by Equations (B-1) and (B-11) are compared, we have EQU y.sub.i =R.multidot.X.sub.i mod N (i=0, 1, 2, . . . ) (B-12)
and the sequence y.sub.i (i=0, 1, 2, . . . ) generated by Equation (B-11) is obtained by multiplying the sequence X.sub.i (i=0, 1, 2 . . . ) generated by Equation (B-1) by R. Accordingly, in order to generate b.sub.i, which is a series of the least significant bit of X.sub.i, as a pseudorandom number sequence which is cryptologically secure, it is required that the following operation be performed with regard to Yi obtained by computation: EQU X.sub.i =R.sup.-1 .multidot.y.sub.i mod N (i=0, 1, 2, . . . )(B-13)
Equation (B-3) can be executed by repeating the modular exponentiation operation indicated by Equation (B-5). More specifically, the procedure for successively computing modular exponentiation x.sub.i+1 =x.sub.i.sup.e mod N (i=0, 1, 2, . . . ) by repeating modular multiplication is as indicated by "Algorithm 1" below. It should be noted that e is an integer comprising k bits and. is represented by e=[e.sub.k, e.sub.k-1, . . . e.sub.2, e.sub.1 ]. ##EQU1##
With the INPUT statement of line (**1), values of x.sub.0, e, N, s are entered. Here s is the iteration number of the residual operation. The FOR statement of line (**2) is a command for repeating the processing up to line (**9) from "0" to "s" in relation to the function i. This statement causes repetition of processing for successively obtaining the modular exponentiation x.sub.i+1 (i=0, 1, 2, . . . ,s).
The procedure for computing the modular exponentiation x.sub.i+1 =x.sup.i.sup.e mod N by repeating modular multiplication using the computation procedure of the Montgomery method is as shown below. It should be noted that R is a relatively prime integer with respect to N and e is an integer comprising k bits, as mentioned earlier, where e=[e.sub.k, e.sub.k-1, . . . e.sub.2, e.sub.1 ]. If this algorithm is executed, the series x.sub.i (i=0, 1, 2, . . . ,s), which is obtained by Equation (B-2), can be acquired. ##EQU2##
In a case where Equation (B-2) is computed by the Montgomery method in accordance with Algorithm 2, the series y.sub.i+1 (i=0, 1, 2, . . . , s) obtained as the output of the FOR-NEXT portion with respect to j is represented by EQU y.sub.0 =R.multidot.x.sub.0 mod N (B-14) EQU y.sub.i+1 =R.sup.-(e-1) .multidot.y.sub.i.sup.e mod N (i=0, 1, 2, . . . )(B-15)
using the same parameters as in Equation (B-1) and R, which is a relatively prime number with respect to N.
In this case, when the sequence x.sub.i+1 (i=0, 1, 2, . . . ) generated by Equation (B-3) and the sequence y.sub.i+1 (i=0, 1, 2, . . . ) generated by Equation (B-15) are compared, we have EQU y.sub.i =R.multidot.X.sub.i mod N (i=0, 1, 2, . . . ). (B-16)
In other words, in a case where Equation (B-3) is computed by the Montgomery method in accordance with Algorithm 2, the sequence Yi+l (i=0, 1, 2, . . . s) obtained as the output of the FOR-NEXT portion with respect to j is the relation of Equation (B-16) with regard to the sequence x.sub.i+1 (i=0, 1, 2, . . . s) obtained by Equation (B-3).
Accordingly, in order to obtain the operational result x.sub.i+1 (x.sub.i.sup.e mod N), which is obtained by Algorithm 1 of a modular exponentiation operation which does not employ the Montgomery method with regard to the input x.sub.i, by Algorithm 2 of a modular exponentiation operation which does employ the Montgomery method, it is necessary to correct x.sub.i to y.sub.i =Mont (x.sub.i,R.sub.R) (=R.multidot.x.sub.i mod N) by the equation (*1) of Algorithm 2 and correct y.sub.i+1, which is obtained as the output of the FOR-NEXT portion with respect to j to x.sub.i+1 =Mont (y.sub.i+1, 1) (=R.sup.-1 .multidot.y.sub.i+1 mod N) by equation (*3).
However, in a case where the secure pseudorandom number generating method described above is used, it is required that p, q be made several hundred bits. As a result, a large amount of computation is involved. In particular, the amount of computation for the portions of Equations (B-1), (B-3) is large. Consequently, pseudorandom numbers Cannot be generated at high speed and generation/reproduction of communication data cannot be performed at a high speed on the basis of these pseudo-random numbers.